package com.lh.nk;

import java.util.Stack;

/**
 * @author: linghao
 * @since: 2023/1/27
 *
 * 描述
 * 给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。
 *
 * 例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .
 * 例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .
 */
public class 最长的括号子串NC49 {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()(()()((((((())("));
    }

    public static int longestValidParentheses (String s) {
        // write code here
        int max = 0;
        //记录上次连续括号的结束位置
        int temp = -1;
        if(s.isEmpty())return 0;
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            switch (c){
                case '(':
                    stack.push(i);
                    break;
                case ')':
                    if(stack.isEmpty()){
                        temp = i;
                    }else{
                        stack.pop();
                        //说明栈中还有左括号，右括号不够,需要减去栈顶位置
                        if(!stack.isEmpty()){
                            max = Math.max(max,i-stack.peek());
                        }else{ //减去上一次结束的位置
                            max = Math.max(max,i-temp);
                        }
                    }
            }
        }
        return  max;
    }
}
